package LearnAlgorithm.e_多维数组and矩阵;


public class d二维正方01数组求最大1围成的正方形plus3点查4数优化 {
	public static int[][][] rec = null;
	
	public static void main(String[] args) {
		int[][] matrix = new int[][] {
			{1,1,1,0},
			{1,1,0,1},
			{1,1,0,1},
			{0,1,1,1},
		};
		/*新的数组存放每个元素的位置关系
		{(3,3),(2,4),(1,1),(0,0)},
		{(2,2),(1,3),(0,0),(1,3)},
		{(2,1),(1,2),(0,0),(1,2)},
		{(0,0),(3,1),(2,1),(1,1)},
		 */
		long before = System.currentTimeMillis();
		makeHelpThreeMatrix(matrix);
		printThreeMatrix(rec, matrix.length);
		int findMaxSquare = findMaxSquare(matrix, matrix.length);
		util.Util.duration(before);
		System.out.println(findMaxSquare);
	}
	
	
	
	/**
	 * O(N^3)
	 * @param matrix
	 * @param matrixLength
	 * @return
	 */
	public static int findMaxSquare(int[][] matrix, int matrixLength) {
		int squareLegth = matrixLength;//默认矩阵长度是最大正方形长度；
		while (squareLegth > 0) {//循环，只要正方形长度>0
			for (int row = 0; row < matrixLength; row++) {//1逐个元素作为顶点
				if (row + (squareLegth - 1) > (matrixLength - 1)) {//如果此顶点的某一个伸展方向不足以构成当前squareLength长度的正方形
					break;//那么直接大跳出循环
				}
				for (int col = 0; col < matrixLength; col++) {//2以顶点进行四条边伸展判断
					if (col + (squareLegth - 1) > (matrixLength - 1)) {//如果此顶点的某一个伸展方向不足以构成当前squareLength长度的正方形
						break;//那么直接大跳出循环
					}
					if (checkEdge(row,col,squareLegth)) {
						return squareLegth;
					}
				}
			}
			squareLegth--;
		}
		return 0;//没找到就返0
	}
	
	/**
	 * 检查帮助三维数组的坐标
	 * 优化的核心
	 * O(1)
	 * @param row
	 * @param col
	 * @param squareLegth
	 * @return
	 */
	public static boolean checkEdge(int row, int col, int squareLegth) {
		if (
				rec[row][col][0] >= squareLegth &&
				rec[row][col][1] >= squareLegth &&
				rec[row][col + squareLegth - 1][1] >= squareLegth &&
				rec[row + squareLegth - 1][col][0] >= squareLegth
				) {
			return true;
		}
		return false;
	}
	
	/**
	 * 制作存储坐标的三维数组
	 * O(N^2)
	 * @param matrix
	 */
	public static void makeHelpThreeMatrix(int[][] matrix) {
		int length = matrix.length;//因为是matrix正方形所以声明一条边的长度就够了
		rec = new int[length][length][2];
		//初始化最后一行
		int currentRow = length - 1;//定义当前行指针
		for (int col = length - 1; col >= 0; col--) {//从右向左遍历当前行
			int value = matrix[currentRow][col];
			if (value == 1) {//当前遍历元素值=1
				if (col == length - 1) {//如果元素位于最右
					rec[currentRow][col][0] = 1;//把坐标x初始化成1
				} else {
					rec[currentRow][col][0] = rec[currentRow][col + 1][0] + 1;//不位于最右；“此元素坐标x”=“此元素右方第一个元素的“x坐标值+1””
				}
				rec[currentRow][col][1] = 1;//最后一行每一个值=1的元素的y坐标都初始化成1
			}
		}
		currentRow--;//当前行离开最后一行来到倒数第二行
		for (int row = currentRow; row >= 0; row--) {//开始逐行
			for (int col = length - 1; col >= 0; col--) {//开始逐列遍历
				int value = matrix[row][col];
				if (value == 1) {//当前遍历元素值=1
					if (col == length - 1) {//如果元素位于最右
						rec[row][col][0] = 1;//把坐标x初始化成1
					} else {
						rec[row][col][0] = rec[row][col + 1][0] + 1;//不位于最右；“此元素坐标x”=“此元素右方第一个元素的“x坐标值+1””
					}
					//下面的if判断可以总结成一行代码：rec[row][col][1] = rec[row + 1][col][1] + 1;
					if (matrix[row + 1][col] == 1) {//此元素A下方一个元素B的值=1
						rec[row][col][1] = rec[row + 1][col][1] + 1;//A的坐标y=B的坐标y+1
					} else {
						rec[row][col][1] = 1;//否则初始化成1
					}
				}
			}
		}
	}
	
	/**
	 * 打印三维数组
	 * @param matrix
	 * @param length
	 */
	public static void printThreeMatrix(int[][][] matrix, int length) {
		for (int i = 0; i < length; i++) {
			for (int j = 0; j < length; j++) {
				System.out.print(matrix[i][j][0] + "," + matrix[i][j][1] + "\t");
			}
			System.out.println();
		}
	}
}
